import numpy as np
from sklearn.cluster import DBSCAN
from scipy.spatial.distance import jensenshannon

def calculate_jsd_matrix(features):
    """计算Jensen-Shannon距离矩阵"""
    n = len(features)
    dist_matrix = np.zeros((n, n))
    
    for i in range(n):
        for j in range(n):
            dist_matrix[i, j] = jensenshannon(features[i], features[j])
    
    return dist_matrix

def AS_DBSCAN(features, eps=0.3, min_samples=5):
    """
    Algorithm 2: Adaptive Sparse DBSCAN
    实现论文中的自适应DBSCAN聚类
    """
    # 步骤1：稀疏梯度提取和量化（简化版）
    # 在实际实现中需要添加TopK和量化逻辑
    
    # 步骤2：计算JSD相似度矩阵
    jsd_matrix = calculate_jsd_matrix(features)
    
    # 步骤3：自适应参数调整
    mean_dist = np.mean(jsd_matrix)
    std_dist = np.std(jsd_matrix)
    eps_adaptive = mean_dist + std_dist
    min_samples_adaptive = max(3, int(0.3 * len(features)))
    
    # 步骤4：密度聚类
    clustering = DBSCAN(
        eps=eps_adaptive, 
        min_samples=min_samples_adaptive,
        metric='precomputed'
    ).fit(jsd_matrix)
    
    # 步骤5：簇合并优化
    clusters = {}
    for label in set(clustering.labels_):
        if label == -1:  # 噪声点
            continue
        clusters[label] = np.where(clustering.labels_ == label)[0].tolist()
    
    return list(clusters.values())
